/* qsort.c */

/* Enzo Ferber : <enzo@veloxmail.com.br>
*
* Quick Sort Routine Example
* sep 2010
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

/* compare function for quick sort */
int compare ( const void *va, const void *vb )
{
   int *a = (int *) va;
   int *b = (int *) vb;
   
   return (*a > *b) ? 1 : ( *a == *b ) ? 0 : -1 ;
}

int *buildarray ( void )
{
   /* information */
   int *p, i = 1, n;

   p = ( int * ) malloc ( 2 * sizeof ( int ));
   if ( !p )
   {
      perror ( "[*] malloc" );
      return NULL;
   }
   
   while ( 1 )
   {
      printf ( "Value[%3d]: ", i ); __fpurge ( stdin );
      scanf ( "%d", &n );

      /* first element will be the number of elements on the array
       * this will be used by qsort()
       */
      if ( n < 0 )
      {
         /* first element */
         *p = i - 1;
         return p;
      }
      else *(p + i) = n;

      /* alloc memory for the next item */
      p = ( int * ) realloc ( p, (i + 2) * sizeof(int));
      if ( !p )
      {
         perror ( "[*] realloc" );
         return NULL;
      }

      /* increment */
      ++i;
   }
   return p;
}

int main ( void )
{
   int *a = buildarray();
   int *p, n, i;

   n = *(a + 0);
   p = a + 1;
   
   /* Explanation:
    *
    * 'a' after buildarray return is:
    *
    * 'a'pos: 0             1      2      3      n
    * [number_of_elements][data][data1][data2][dataN]....
    *
    * Value:  n             x      x      x      x
    *
    * So, 'n' is the number of elements in the array, and 'x'
    * is the data entered by the user. Pretty easy huh?
    *
    * So now, we do:
    *
    * p = a[1]
    * n = a[0]
    * Therefore,
    *
    * p[0] = a[1];
    * n = n; (local_n) = (n_in_number_of_elements)
    *
    * P now is an array with only data entered by the user
    */
   
   /* now we organize the array in ascending order */
   printf ( "Sorting...\n" );   
   qsort ( (void *)p, n, sizeof(int), compare );

   printf ( "Array: " );
   for ( i = 0; i < n; i++ ) printf ( "%d ", p[i] );
   printf ( "\n" );

   /* free() the memory */
   free ( a );   
   
   /* return to SO */
   return 0;
}